package com.explorati.LeetCode26.removeDuplicates;

/**
 * LeetCode26：给定一个有序数组，去除重复元素并返回最后数组长度
 * 
 * Given nums = [1,1,2], Your function should return length = 2, with the first
 * two elements of nums being 1 and 2 respectively. It doesn't matter what you
 * leave beyond the returned length. Given nums = [0,0,1,1,1,2,2,3,3,4],
 * 
 * Your function should return length = 5, with the first five elements of nums
 * being modified to 0, 1, 2, 3, and 4 respectively.
 * 
 * @author explorati
 *
 */
public class Solution {
	public int removeDuplicates(int[] nums) {
		// 符合要求元素的最后一个元素位置
		int i = 0;
		// 从第二个元素位置遍历就可以
		for (int j = 1; j < nums.length; j++) {
			// 如果当前位置元素大于符合要求数组中最大位置元素
			if (nums[j] > nums[i]) {
				if (i != j) {
					// 和第一个不符合条件的元素交换位置
					swap(nums, ++i, j);
				} else {
					i++;
				}
			}
			// 如果当前元素等于数组中最大元素，即i所指元素，直接j++
		}
		return i + 1;
	}

	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}
